﻿/*
forward_list(单向链表)，是序列容器。允许在序列中的任何地方快速的插入和擦除动作。
数据结构：由一个指向下一个元素地址的指针和元素类型组成。

插入和删除的时间复杂度为 O(1)
查找的时间复杂度为 O(N)

*/

#include <iostream>
#include <forward_list>


void flist_print(std::forward_list<int> &flist)
{
	for (int& x : flist)
		std::cout << ' ' << x;

	std::cout << "\n";
}

void test_ctor()
{
	std::forward_list<int> frist;
	std::forward_list<int> second(5);//默认为0 ，容器内由 5个0

	std::forward_list<int> third(5, 5);

	for (auto &i : third) std::cout << " " <<  i ;
	std::cout << "\n";

	for (auto &i : second) std::cout << " " << i;
	std::cout << "\n";

	std::forward_list<int> fourth(third);
	flist_print(fourth);
	std::forward_list<int> fiveth(std::move(fourth));

	std::forward_list<int> sixth({1,2,3,4,5});

	flist_print(fiveth);
	flist_print(sixth);
}

void flist_begin()
{
	std::forward_list<int> list = { 1,2,3,4,5 };
	
	for (auto it = list.cbegin(); it != list.cend(); it++)
	{
		
		std::cout << "  " << *it;
	}
	std::cout << "\n";


	for (auto it = list.begin(); it != list.end(); it++)
	{
		*it = *it +1;
		std::cout << " " << *it;
	}

	if (list.empty()) {
		std::cout << "list is empty" << std::endl;
	}
	else {
		std::cout << "list is not empty" << std::endl;
	}

	std::cout << "list max_size:" << list.max_size() << std::endl;

	list.push_front(111);

	list.emplace_front(222);//或许雷同与 vector 的 insert 和 emplace 相同，前者需要额外的拷贝/析构 或者 move 

	flist_print(list);

}

using std::cout;
using std::endl;
using std::forward_list;

void test_forward_list()
{
	cout << "\n fowward_list...\n" << endl;

	forward_list<long>  c;

	for (long i = 0; i < 100000; i++)
	{
		try
		{
			c.push_front(rand());
		}
		catch (const std::exception& p)
		{
			cout << p.what() << endl;
			abort();
		}
	}
	

	cout << "c.max_size(): " << c.max_size();
	cout << "c.front:=" << c.front();
}

int main(void)
{
	//test_ctor();
	//flist_begin();
	return 0;
}